package oj;

import java.util.HashMap;
import java.util.Map;

public class Num110 {
    //使用Map来优化使用递归求高度的低效
    Map<TreeNode,Integer> map=new HashMap<>();
    //将节点和每个节点的高度存在map里
    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        int leftHeight=0;
        int rightHeight=0;
        if(map.containsKey(root.left)){
            //root.left的高度已经求过了，直接从map中取出
            leftHeight=map.get(root.left);
        }else {
            //这个节点没有出现过，就通过递归函数将这个节点和它的高度存入
            leftHeight=maxDepth(root.left);
            map.put(root.left,leftHeight);
        }

        //右子树与左子树的求法相同
        if(map.containsKey(root.right)){
            leftHeight=map.get(root.right);
        }else {
            leftHeight=maxDepth(root.right);
            map.put(root.right,leftHeight);
        }
//        int leftHeight=maxDepth(root.left);
//        int rightHeight=maxDepth(root.right);
        int abs=Math.abs(leftHeight-rightHeight);
        if(abs>1){
            return false;
        }
        //递归去看左右子树是否平衡树
        return isBalanced(root.left) && isBalanced(root.right);
    }
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 1;
        }
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));

    }
}
